package leetcode每日一题;

/**
 * 1. 问题描述
 *      长度为n的数组，其中的元素范围在0~n-1之间，找出其中一个重复出现的元素
 *
 * 2. 算法分析
 *      原地置换法
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 找出数组中的一个重复元素 {
    public static void main(String[] args) {
        int[] nums = {2,0,3,1};
        int[] sortedOrgin = sortedOrgin(nums);
        for (int i : sortedOrgin) {
            System.out.print(i+" ");
        }
    }

    // 采用原地置换法进行排序
    public static int[] sortedOrgin(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == i) {
                continue;
            }
            int m = nums[i];
            if (nums[m] != m) {
                // 进行交换
                nums[i] = nums[m];
                nums[m] = m;
            }
        }
        return nums;
    }

    public static int findRepeatNumber(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] == i) {
                continue;
            }
            int m = nums[i];
            if (m == nums[m]) {
                // 此时说明两个不同位置上的值相同
                return m;
            }
            // 此时需要进行交换   nums[i] nums[nums[i]]=nums[m] 之间交换
            nums[i] = nums[m];
            nums[m] = m;
        }
        return -1;
    }
}
